package com.daji.base_data_structure.Tree.red_black_tree;

import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;

/* 
 * 左偏型红黑树的代码实现
 * 参考资料：黑马数据结构 —— 红黑树
 * 已经全部实现，后续只需要复习即可。
 * TODO 这个类是严格面向对象设计的，非常严谨。如果看不懂去看LinkList.java这个类，一样的设计方式。
 * FIXME 没有提供删除的API。删除的实现较为复杂，待日后填充吧
 */
public class Left_RedBlackTree<Key extends Comparable<Key>, Value> {
    //根节点
    //TODO 这个类是严格面向对象设计的，非常严谨。如果看不懂去看LinkList.java这个类，一样的设计方式。
    private Node root;  
    //记录树中元素的个数
    private int SIZE;
    //红色链接
    private static final boolean RED = true;
    //黑色链接
    private static final boolean BLACK = false;


    //结点类
    public class Node {
        //存储键
        public Key key;
        //存储值
        public Value value;
        //记录左子结点
        public Node left;
        //记录右子结点
        public Node right;
        //由其父结点指向它的链接的颜色
        public boolean color;

        public Node(Key key, Value value, Node left, Node right, boolean color) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
            this.color = color;
        }
    }


    //获取树中元素的个数
    public int size() {
        return SIZE;
    }


    /**
     * 判断当前节点是否为红色结点
     *
     * @param x
     * @return
     */
    private boolean isRed(Node x) {
        if (x==null){
            return false;
        }
        //如果是红色返回TRUE
        return x.color==RED;
    }

    /**
     * 左旋转
     * 【插入新的结点出现红色右连接且该结点左连接为黑色】左旋（X结点左黑右红，左旋转X结点）
     * 【大吉】已经覆写完毕
     * @param node
     * @return
     */
    private Node rotateLeft(Node node) {

        Node RIGHT = node.right;    //RIGHT:该结点的右结点
        //“断键重组”操作，RIGHT的左结点断裂，直接赋值给node的右结点即可
        node.right = RIGHT.left;
        //左旋动作
        RIGHT.left = node;
        //颜色根据链条的指向进行重组
        RIGHT.color = node.color;    //让RIGHT结点的color属性变为原结点的color属性
        node.color = RED;       //新加入的结点总是红色的
        return RIGHT;
    }

    /**
     * 右旋（连续左红即右旋）
     * 当出现本结点的左儿子和左左儿子全部都是红色情形（连续红节点），右旋该结点
     * 【大吉】已经覆写完毕
     *
     * @param node
     * @return
     */
    private Node rotateRight(Node node) {

        Node LEFT = node.left;//找到该节点的左结点
        //“断键重组”操作，LEFT的右结点断裂，直接赋值给node的右结点即可
        node.left = LEFT.right;
        //右旋动作
        LEFT.right = node;
        //颜色根据链条的指向进行重组
        LEFT.color = node.color;    //让LEFT结点的color属性变为原结点的color属性
        node.color = RED;       //新加入的结点总是红色的
        return LEFT;
    }

    /**
     * 颜色反转,相当于完成拆分4-节点
     * 当一个结点的左右子树的颜色全部都是RED，也就是出现了临时的4结点，只需要把这三个结点进行颜色反转即可。
     * 【注意】如果颜色反转出现在整棵树的顶点头结点，那么就全部置为黑色结点（三个黑）
     * 【大吉】已经覆写完毕
     *
     * @param node
     */
    private void flipColors(Node node) {
        //TODO 判断是否入参是整个树的顶点。黑马版本暂时无法判断，所以写个空，以后有机会实现
        /* 
            if (node == head){
                //TODO 全部变成黑色结点
                node.color = BLACK;
                node.left.color=BLACK;
                node.right.color = BLACK;
            }
         */
        //当前结点变为红色
        node.color = RED;
        //左子结点和右子结点变为黑色
        node.left.color=BLACK;
        node.right.color = BLACK;
    }

    /**
     * 在整个树上完成插入操作
     * 和底下的方法的区别：由于这颗红黑树的root结点并不是第一个结点，root
     *
     * @param key
     * @param val
     */
    public void put(Key key, Value val) {
        root = put(root,key,val);
        //根结点的颜色总是黑色。这一步其实没错，root永永远远就是根结点。不信看重载方法的返回结果就行了。
        root.color = BLACK; 
    }

    /**
     * 在指定树中，完成插入操作,并返回添加元素后新的树
     * 注意，这是个私有方法
     * 运用了非常巧妙的递归操作，认真看。
     * 较难实现
     *
     * @param node
     * @param key
     * @param val
     */
    private Node put(Node node, Key key, Value val) {
        //判断node是否为空，如果为空则直接返回一个红色的结点就可以了（新插入的结点必红）
        if (node == null){
            //数量+1
            SIZE++;
            return new Node(key,val,null,null,RED);
        }

        //比较node结点的键和key的大小
        int cmp = key.compareTo(node.key);
        if (cmp<0){
            //继续递归往左
            node.left = put(node.left,key,val);

        }else if (cmp>0){
            //继续递归往右
            node.right = put(node.right,key,val);

        }else{
            //发生值的替换（这里其实是仿照map的设计，如果map有相同的key，那么就替换value）
            //如果不设计成map的API，只管插入Integer，就没有这个必要了
            //不是红黑树的实现重点。只是黑马仿照了map设计而已
            node.value = val;
        }
        //【重点】从这里往下其实都是递归执行了，包括上面也是递归的。所以该方法可以实现递归旋转整棵树
        //【重点】从这里往下其实都是递归执行了，包括上面也是递归的。所以该方法可以实现递归旋转整棵树
        //【重点】从这里往下其实都是递归执行了，包括上面也是递归的。所以该方法可以实现递归旋转整棵树
        //【重点】从这里往下其实都是递归执行了，包括上面也是递归的。所以该方法可以实现递归旋转整棵树

        //颜色反转：当前结点的左子结点和右子结点都为红色时，需要颜色反转
        //优先判断颜色翻转情形。
        //注意特殊情形：如果出现X左右都是红色情形，那么无需任何旋转，直接颜色反转即可（该特殊情形为大吉总结，黑马版并没有写）
        if (isRed(node.left) && isRed(node.right)){
            flipColors(node);
        }

        //进行左旋:当当前结点node的左子结点为黑色，右子结点为红色，需要左旋
        if (isRed(node.right) && !isRed(node.left)){
            node = rotateLeft(node);
        }

        //进行右旋：当当前结点node的左子结点和左子结点的左子结点都为红色，需要右旋
        //这里的判断条件只能这样写，如果&&符号的两侧条件翻转，就会导致空指针的发生！
        //这里的判断条件只能这样写，如果&&符号的两侧条件翻转，就会导致空指针的发生！
        //这里的判断条件只能这样写，如果&&符号的两侧条件翻转，就会导致空指针的发生！
        if (isRed(node.left) && isRed(node.left.left)){
            node = rotateRight(node);
        }

        /*
            这个return，可能经过各种旋转操作改变了"根（root）"的结点位置
            但是其对于调用者来说，其永远就代表着"根（root）"结点。
            好好体会这里递归的妙处。
        */
        return node;
    }

    //根据key，从树中找出对应的值
    //很简单。就是调用二分查找嘛
    public Node get(Key key) {
        return get(root,key);
    }

    //从指定的树x中，查找key对应的值
    //很简单。就是递归二分查找嘛，没什么好说的了
    public Node get(Node x, Key key) {
        if (x == null){
            return null;
        }

        //比较x结点的键和key的大小
        int cmp = key.compareTo(x.key);
        if (cmp<0){
            return get(x.left,key);
        }else if (cmp>0){
            return get(x.right,key);
        }else{
           return x;
        }

    }

    /**
     * BST的中序遍历，就是按照顺序输出元素。
     * @return 返回按照升序输出的Node集合。
     */
    public List<Node> getOrderArray(){
        List<Node> withOrder = new LinkedList<>();
        inOrderTraverse(root,withOrder);
        return withOrder;
    }

    private void inOrderTraverse(Node node, List<Node> list){
        if(node == null){
            return;
        }
        //左根右
        inOrderTraverse(node.left, list);
        list.add(node);
        inOrderTraverse(node.right, list);
    }

    /**
     * Removes the smallest key and associated value from the symbol table.
     *
     * @throws NoSuchElementException if the symbol table is empty
     */
    public void deleteMin() {
        if (root == null)
            throw new NoSuchElementException("BST underflow");

        // if both children of root are black, set root to red
        if (!isRed(root.left) && !isRed(root.right))
            root.color = RED;

        root = deleteMin(root);
        if (root != null)
            root.color = BLACK;
        // assert check();
    }

    // delete the key-value pair with the minimum key rooted at h
    private Node deleteMin(Node h) {
        // 相当于删掉else branch的delete
        if (h.left == null)
            return null;

        if (!isRed(h.left) && !isRed(h.left.left))
            h = moveRedLeft(h);

        h.left = deleteMin(h.left);
        return balance(h);
    }

    /* 
     * Assuming that h is red and both h.left and h.left.left
     * are black, make h.left or one of its children red.
     * 向左填红
     * 
     * 对上面英文的解释：
     * 为了维持【隐藏约束】
     * 我们先让h
     * moveRedRight相似
     */
    private Node moveRedLeft(Node h) {
        // assert (h != null);
        // assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);

        flipColors(h); // h.left变红
        if (isRed(h.right.left)) {
            // 如果右孩子出现双红矛盾，则通过rotate+flip来解决
            // 原来的h被转到h.left
            h.right = rotateRight(h.right);
            h = rotateLeft(h);
            flipColors(h);
        }
        // 最终h.left或者h.left.left为红。h.right可能为红，可以事后调用balance消除。
        return h;
    }

    // Assuming that h is red and both h.right and h.right.left
    // are black, make h.right or one of its children red.
    // 向右填红
    private Node moveRedRight(Node h) {
        // assert (h != null);
        // assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);
        flipColors(h);
        if (isRed(h.left.left)) {
            h = rotateRight(h);
            flipColors(h);
        }
        return h;
    }

    /**
     * Removes the largest key and associated value from the symbol table.
     *
     * @throws NoSuchElementException if the symbol table is empty
     */
    public void deleteMax() {
        if (root == null)
            throw new NoSuchElementException("BST underflow");

        // if both children of root are black, set root to red
        if (!isRed(root.left) && !isRed(root.right))
            root.color = RED;

        root = deleteMax(root);
        if (root != null)
            root.color = BLACK;
        // assert check();
    }

    // delete the key-value pair with the maximum key rooted at h
    private Node deleteMax(Node h) {
        if (isRed(h.left))
            h = rotateRight(h);

        if (h.right == null)
            return null;

        if (!isRed(h.right) && !isRed(h.right.left))
            h = moveRedRight(h);

        h.right = deleteMax(h.right);

        return balance(h);
    }

    

    /**
     * Removes the specified key and its associated value from this symbol table
     * (if the key is in this symbol table).
     *
     * @param key the key
     * @throws IllegalArgumentException if {@code key} is {@code null}
     */
    public void delete(Key key) {
        if (key == null)
            throw new IllegalArgumentException("argument to delete() is null");
        //RBT中压根就没有该键对应的Node
        if (get(key) == null) 
            return;

        // if both children of root are black, set root to red
        if (!isRed(root.left) && !isRed(root.right))
            root.color = RED;

        root = delete(root, key);
        if (root != null)
            root.color = BLACK;
        // assert check();
    }

    // delete the key-value pair with the given key rooted at h
    private Node delete(Node h, Key key) {
        // assert get(h, key) != null;

        if (key.compareTo(h.key) < 0) {
            if (!isRed(h.left) && !isRed(h.left.left))
            // 此时h为红h.left为黑，moveRedLeft把红色推到左子树以便调用下面的delete
                h = moveRedLeft(h);
            h.left = delete(h.left, key);
        } else {
            if (isRed(h.left))
            // 如果h.left为红则右旋，使h.right变红，方便从右子树里删除
                h = rotateRight(h);
            // 此时h为红或者h.right为红。
            if (key.compareTo(h.key) == 0 && (h.right == null))
                // h.right == null所以上面的旋转没有发生
                // 右子树null，左子树不为红，只能也是null，不然黑高不平衡
                return null;
            // 要删的结点在右子树
            // 如果要删的是h，与右子树的min对调key-value后删除右子树的min
            if (!isRed(h.right) && !isRed(h.right.left))
                // h.right不为红，h必定为红
                // 与上面的moveRedLeft相似，把红色推到右子树以便接下来在里面delete
                h = moveRedRight(h);
            // 常规的BST删除逻辑
            if (key.compareTo(h.key) == 0) {
                Node x = findSuccessor(h.right);
                h.key = x.key;
                h.value = x.value;
                // h.val = get(h.right, min(h.right).key);
                // h.key = min(h.right).key;
                h.right = deleteMin(h.right);
            } else
                h.right = delete(h.right, key);
        }
        // 修复moveRedLeft，moveRedRight的副作用：h.right可能会变红
        return balance(h);
    }

    private Node balance(Node h) {
        // assert (h != null);
        if (isRed(h.right))                      
            h = rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left)) 
            h = rotateRight(h);
        if (isRed(h.left) && isRed(h.right))
            flipColors(h);

        //h.size = size(h.left) + size(h.right) + 1;
        return h;
    }

    /**
     * 找到该节点的后继结点(successor)
     * 找successor，就是找该结点的右结点（如果有的话），并将该节点的右结点
     * 看作是一颗新的二叉搜索树，然后找到该二叉搜索树最小的结点，该结点就是successor
     * 体现了找“比我大的最小结点”的思想
     * RBT当然也是二叉搜索树，也适用
     * @param node
     * @return
     */
    public Node findSuccessor(Node node) {
        if (node.right == null) {  //如果没有右结点，该节点的successor肯定在它上面，所以用该方法是找不到的。
            return null;
        }
        //往右走一步
        node = node.right;
        //找最左的结点
        while (true){
            if (node.left != null) {
                node = node.left;
            }else {
                break;
            }
        }
        return node;
    }

}
